package greedy;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description: 56. 合并区间
 * User: Li_yizYa
 * Date: 2025/6/27
 * Time: 11:34
 */
public class Solution15 {
    /**
     * 不改变原数组
     * @param intervals
     * @return
     */
    public int[][] merge1(int[][] intervals) {
        if (intervals == null || intervals.length == 0) {
            return new int[0][0];
        }
        Arrays.sort(intervals, (a, b) -> {
            return a[0] - b[0];
        });
        List<int[]> tmp = new ArrayList<>();
        int start = intervals[0][0];
        int end = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if (end >= intervals[i][0]) {
                end = Math.max(end, intervals[i][1]);
            } else {
                tmp.add(new int[]{start, end});
                start = intervals[i][0];
                end = intervals[i][1];
            }
        }
        tmp.add(new int[]{start, end});
        return tmp.toArray(new int[tmp.size()][]);
    }
    /**
     * 改变原数组
     * @param intervals
     * @return
     */
    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length == 0) {
            return new int[0][0];
        }
        Arrays.sort(intervals, (a, b) -> {
            return a[0] - b[0];
        });
        List<int[]> tmp = new ArrayList<>();
        int index = 0;
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[index][1] >= intervals[i][0]) {
                intervals[index][1] = Math.max(intervals[index][1], intervals[i][1]);
            } else {
                tmp.add(intervals[index]);
                index = i;
            }
        }
        tmp.add(intervals[index]);
        return tmp.toArray(new int[tmp.size()][]);
    }
}
